package canMakeArithmeticProgression;

import java.util.*;

public class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        // 思路 简单题 简单做 直接排序
//        Arrays.sort(arr);
//        int d = arr[1]-arr[0];
//        for (int i = 2; i < arr.length; i++) {
//            if(arr[i]-arr[i-1]!=d){
//                return false;
//            }
//        }
//        return true;

        // O(n)复杂度实现
        // 先求出公差d 最小项和次小项的差 求出通项公式
        // 再用Hash表计数，判断数列的每一项是否都有
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if(min1>arr[i]){
                min2 = min1;
                min1 = arr[i];
            }else if(min2>arr[i]){
                min2 = arr[i];
            }
            set.add(arr[i]);
        }
        int d = min2 - min1; // 公差
        if(d==0){
            return set.size()==arr.length;
        }
        for (int i = 0; i < arr.length; i++) {
            int a = min1+d*i;
            if(!set.contains(a)){
                return false;
            }
        }
        return set.size()==arr.length?true:d==0;
    }
}
